import java.util.*;


public class LeetCode103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        //创建一个队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        //向队列尾插入值
        queue.offer(root);
        //定义一个变量用于判断是奇书层还是偶数层
        boolean leftToRight = true;
        int c1 = 1;//用于记录当前根节点
        //循环判断队列到为空结束
        while (!queue.isEmpty()) {
            int c2 = 0;// 用于记录下一层的节点数量
            //创建一个双端队列
            LinkedList<Integer> list = new LinkedList<>();
            //用于记录根节点的左子节点 右子节点
            for (int i = 0; i < c1; i++) {
                //从对列头获取值, 并移除
                TreeNode node = queue.poll();
                //奇数层向对队头添加  偶数层向队尾添加
                if (leftToRight) {
                    list.offerLast(node.val);
                } else {
                    list.offerFirst(node.val);
                }
                //判断当前根节点 是否有左子节点 右子节点
                if (node.left != null) {
                    //有的话，添加到队列中
                    queue.offer(node.left);
                    c2++;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    c2++;
                }
            }
            c1 = c2;
            leftToRight = !leftToRight;
            result.add(list);
        }


        return result;
    }
}
